SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Divide-and-conquer algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Divide-and-conquer algorithm</span></span>

</h1>

</header>

<p>In <a href="Computer_science" title="Computer science">computer science</a>, <b>divide and conquer</b> is an <a href="Algorithm_design_paradigm" class="mw-redirect" title="Algorithm design paradigm">algorithm design paradigm</a>. A divide-and-conquer <a href="Algorithm" title="Algorithm">algorithm</a> <a href="Recursion_(computer_science)" title="Recursion (computer science)">recursively</a> breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

</p><p>The divide-and-conquer technique is the basis of efficient algorithms for many problems, such as <a href="Sorting_algorithm" title="Sorting algorithm">sorting</a> (e.g., <a href="Quicksort" title="Quicksort">quicksort</a>, <a href="Merge_sort" title="Merge sort">merge sort</a>), <a href="Multiplication_algorithm" title="Multiplication algorithm">multiplying large numbers</a> (e.g., the <a href="Karatsuba_algorithm" title="Karatsuba algorithm">Karatsuba algorithm</a>), finding the <a href="Closest_pair_of_points_problem" title="Closest pair of points problem">closest pair of points</a>, <a href="Syntactic_analysis" class="mw-redirect" title="Syntactic analysis">syntactic analysis</a> (e.g., <a href="Top-down_parser" class="mw-redirect" title="Top-down parser">top-down parsers</a>), and computing the <a href="Discrete_Fourier_transform" title="Discrete Fourier transform">discrete Fourier transform</a> (<a href="Fast_Fourier_transform" title="Fast Fourier transform">FFT</a>).<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p><p>Designing efficient divide-and-conquer algorithms can be difficult. As in <a href="Mathematical_induction" title="Mathematical induction">mathematical induction</a>, it is often necessary to generalize the problem to make it amenable to a <a href="Recursion_(computer_science)" title="Recursion (computer science)">recursive</a> solution. The correctness of a divide-and-conquer algorithm is usually proved by mathematical induction, and its computational cost is often determined by solving <a href="Recurrence_relation" title="Recurrence relation">recurrence relations</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Divide_and_conquer">Divide and conquer</h2></div>

<p>The divide-and-conquer <a href="Programming_paradigm" title="Programming paradigm">paradigm</a> is often used to find an optimal solution of a problem. Its basic idea is to decompose a given problem into two or more similar, but simpler, subproblems, to solve them in turn, and to compose their solutions to solve the given problem. Problems of sufficient simplicity are solved directly.

For example, to sort a given list of <i>n</i> <a href="Natural_number" title="Natural number">natural numbers</a>, split it into two lists of about <i>n</i>/2 numbers each, sort each of them in turn, and interleave both results appropriately to obtain the sorted version of the given list (see the picture). This approach is known as the <a href="Merge_sort" title="Merge sort">merge sort</a> algorithm.

</p><p>The name "divide and conquer" is sometimes applied to algorithms that reduce each problem to only one sub-problem, such as the <a href="Binary_search" title="Binary search">binary search</a> algorithm for finding a record in a sorted list (or its analogue in <a href="Numerical_algorithm" class="mw-redirect" title="Numerical algorithm">numerical computing</a>, the <a href="Bisection_algorithm" class="mw-redirect" title="Bisection algorithm">bisection algorithm</a> for <a href="Root-finding_algorithm" title="Root-finding algorithm">root finding</a>).<sup id="cite_ref-CormenLeiserson2009_2-0" class="reference"><a href="#cite_note-CormenLeiserson2009-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> These algorithms can be implemented more efficiently than general divide-and-conquer algorithms; in particular, if they use <a href="Tail_recursion" class="mw-redirect" title="Tail recursion">tail recursion</a>, they can be converted into simple <a href="Loop_(computing)" class="mw-redirect" title="Loop (computing)">loops</a>. Under this broad definition, however, every algorithm that uses recursion or loops could be regarded as a "divide-and-conquer algorithm". Therefore, some authors consider that the name "divide and conquer" should be used only when each problem may generate two or more subproblems.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> The name <b>decrease and conquer</b> has been proposed instead for the single-subproblem class.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</p><p>An important application of divide and conquer is in optimization, where if the search space is reduced ("pruned") by a constant factor at each step, the overall algorithm has the same asymptotic complexity as the pruning step, with the constant depending on the pruning factor (by summing the <a href="Geometric_series" title="Geometric series">geometric series</a>); this is known as <a href="Prune_and_search" title="Prune and search">prune and search</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Early_historical_examples">Early historical examples</h2></div>

<p>Early examples of these algorithms are primarily decrease and conquer – the original problem is successively broken down into <i>single</i> subproblems, and indeed can be solved iteratively.

</p><p><a href="Binary_search_algorithm" class="mw-redirect" title="Binary search algorithm">Binary search</a>, a decrease-and-conquer algorithm where the subproblems are of roughly half the original size, has a long history. While a clear description of the algorithm on computers appeared in 1946 in an article by <a href="John_Mauchly" title="John Mauchly">John Mauchly</a>, the idea of using a sorted list of items to facilitate searching dates back at least as far as <a href="Babylonia" title="Babylonia">Babylonia</a> in 200 BC.<sup id="cite_ref-Knuth3_5-0" class="reference"><a href="#cite_note-Knuth3-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> Another ancient decrease-and-conquer algorithm is the <a href="Euclidean_algorithm" title="Euclidean algorithm">Euclidean algorithm</a> to compute the <a href="Greatest_common_divisor" title="Greatest common divisor">greatest common divisor</a> of two numbers by reducing the numbers to smaller and smaller equivalent subproblems, which dates to several centuries BC.

</p><p>An early example of a divide-and-conquer algorithm with multiple subproblems is <a href="Carl_Friedrich_Gauss" title="Carl Friedrich Gauss">Gauss</a>'s 1805 description of what is now called the <a href="Cooley%E2%80%93Tukey_FFT_algorithm" title="Cooley–Tukey FFT algorithm">Cooley–Tukey fast Fourier transform</a> (FFT) algorithm,<sup id="cite_ref-Heideman84_6-0" class="reference"><a href="#cite_note-Heideman84-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> although he did not <a href="Analysis_of_algorithms" title="Analysis of algorithms">analyze its operation count</a> quantitatively, and FFTs did not become widespread until they were rediscovered over a century later.

</p><p>An early two-subproblem D&C algorithm that was specifically developed for computers and properly analyzed is the <a href="Merge_sort" title="Merge sort">merge sort</a> algorithm, invented by <a href="John_von_Neumann" title="John von Neumann">John von Neumann</a> in 1945.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup>

</p><p>Another notable example is the <a href="Karatsuba_algorithm" title="Karatsuba algorithm">algorithm</a> invented by <a href="Anatolii_Alexeevitch_Karatsuba" class="mw-redirect" title="Anatolii Alexeevitch Karatsuba">Anatolii A. Karatsuba</a> in 1960<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> that could multiply two <i>n</i>-<a href="Units_of_information" title="Units of information">digit</a> numbers in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{\log _{2}3})}">

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{\log _{2}3})}</annotation>

</semantics>

</math></span><img src="./770c7081e94ce7027c145a2f892341605e9b0272.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.352ex; height:3.176ex;" alt="{\displaystyle O(n^{\log _{2}3})}" loading="lazy"></span> operations (in <a href="Big_O_notation" title="Big O notation">Big O notation</a>). This algorithm disproved <a href="Andrey_Kolmogorov" title="Andrey Kolmogorov">Andrey Kolmogorov</a>'s 1956 conjecture that <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega (n^{2})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega (n^{2})}</annotation>

</semantics>

</math></span><img src="./c14304cd1cb8bf603cb59037b666c5a85cd8e7ae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.936ex; height:3.176ex;" alt="{\displaystyle \Omega (n^{2})}" loading="lazy"></span> operations would be required for that task.

</p><p>As another example of a divide-and-conquer algorithm that did not originally involve computers, <a href="Donald_Knuth" title="Donald Knuth">Donald Knuth</a> gives the method a <a href="Post_office" title="Post office">post office</a> typically uses to route mail: letters are sorted into separate bags for different geographical areas, each of these bags is itself sorted into batches for smaller sub-regions, and so on until they are delivered.<sup id="cite_ref-Knuth3_5-1" class="reference"><a href="#cite_note-Knuth3-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> This is related to a <a href="Radix_sort" title="Radix sort">radix sort</a>, described for <a href="IBM_80_series_Card_Sorters" class="mw-redirect" title="IBM 80 series Card Sorters">punch-card sorting</a> machines as early as 1929.<sup id="cite_ref-Knuth3_5-2" class="reference"><a href="#cite_note-Knuth3-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Advantages">Advantages</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Solving_difficult_problems">Solving difficult problems</h3></div>

<p>Divide and conquer is a powerful tool for solving conceptually difficult problems: all it requires is a way of breaking the problem into sub-problems, of solving the trivial cases, and of combining sub-problems to the original problem. Similarly, decrease and conquer only requires reducing the problem to a single smaller problem, such as the classic <a href="Tower_of_Hanoi" title="Tower of Hanoi">Tower of Hanoi</a> puzzle, which reduces moving a tower of height <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> to move a tower of height <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-1}</annotation>

</semantics>

</math></span><img src="./fbd0b0f32b28f51962943ee9ede4fb34198a2521.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.398ex; height:2.343ex;" alt="{\displaystyle n-1}" loading="lazy"></span>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Algorithm_efficiency">Algorithm efficiency</h3></div>

<p>The divide-and-conquer paradigm often helps in the discovery of efficient algorithms. It was the key, for example, to <a href="Karatsuba_algorithm" title="Karatsuba algorithm">Karatsuba</a>'s fast multiplication method, the quicksort and mergesort algorithms, the <a href="Strassen_algorithm" title="Strassen algorithm">Strassen algorithm</a> for <a href="Matrix_multiplication" title="Matrix multiplication">matrix multiplication</a>, and fast Fourier transforms.

</p><p>In all these examples, the D&C approach led to an improvement in the <a href="Asymptotic_complexity" class="mw-redirect" title="Asymptotic complexity">asymptotic cost</a> of the solution. For example, if (a) the <a href="Recursion_(computer_science)" title="Recursion (computer science)">base cases</a> have constant-bounded size, the work of splitting the problem and combining the partial solutions is proportional to the problem's size <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span>, and (b) there is a bounded number <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math></span><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"></span> of sub-problems of size ~ <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {n}{p}}}">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {n}{p}}}</annotation>

</semantics>

</math></span><img src="./b32fd3506523ca103ed9eb0fdd51780648235158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:2.231ex; height:5.176ex;" alt="{\displaystyle {\frac {n}{p}}}" loading="lazy"></span> at each stage, then the cost of the divide-and-conquer algorithm will be <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log _{p}n)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log _{p}n)}</annotation>

</semantics>

</math></span><img src="./1ec332e6a1bd01306f96977220505689e4c578ec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:11.177ex; height:3.176ex;" alt="{\displaystyle O(n\log _{p}n)}" loading="lazy"></span>.

</p><p>For other types of divide-and-conquer approaches, running times can also be generalized. For example, when a) the work of splitting the problem and combining the partial solutions take <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle cn}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle cn}</annotation>

</semantics>

</math></span><img src="./7f0390269a433e7f1a987b5968c6229e43cd7a2b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.402ex; height:1.676ex;" alt="{\displaystyle cn}" loading="lazy"></span> time, where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> is the input size and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math></span><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"></span> is some constant; b) when <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n<2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n<2}</annotation>

</semantics>

</math></span><img src="./34a7846d78a64db4abe69af89c7ef79c249e75ff.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.656ex; height:2.176ex;" alt="{\displaystyle n<2}" loading="lazy"></span>, the algorithm takes time upper-bounded by <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math></span><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"></span>, and c) there are <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q}</annotation>

</semantics>

</math></span><img src="./06809d64fa7c817ffc7e323f85997f783dbdf71d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" loading="lazy"></span> subproblems where each subproblem has size ~ <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {n}{2}}}">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {n}{2}}}</annotation>

</semantics>

</p>

<ul><li>if the number of subproblems <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q>2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q>2}</annotation>

</semantics>

</math></span><img src="./a51ff72f66c28051a819a034dea86997914ab599.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.33ex; height:2.509ex;" alt="{\displaystyle q>2}" loading="lazy"></span>, then the divide-and-conquer algorithm's running time is bounded by <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{\log _{2}q})}">

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{\log _{2}q})}</annotation>

</semantics>

</math></span><img src="./d93c45f148617f5dd55a590a7d91a6a3fb82f002.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.286ex; height:3.176ex;" alt="{\displaystyle O(n^{\log _{2}q})}" loading="lazy"></span>.</li>

<li>if the number of subproblems is exactly one, then the divide-and-conquer algorithm's running time is bounded by <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math></span><img src="./34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy"></span>.<sup id="cite_ref-kleinberg&Tardos_9-0" class="reference"><a href="#cite_note-kleinberg&Tardos-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup></li></ul>

<p>If, instead, the work of splitting the problem and combining the partial solutions take <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle cn^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle cn^{2}}</annotation>

</semantics>

</math></span><img src="./48d6ba2aa952fc4610423a129d41f2c5f3f31c8d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.456ex; height:2.676ex;" alt="{\displaystyle cn^{2}}" loading="lazy"></span> time, and there are 2 subproblems where each has size <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {n}{2}}}">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {n}{2}}}</annotation>

</semantics>

</math></span><img src="./1216d48de276dc45542cb80b1e49037131ec9624.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:2.231ex; height:4.676ex;" alt="{\displaystyle {\frac {n}{2}}}" loading="lazy"></span>, then the running time of the divide-and-conquer algorithm is bounded by <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{2})}</annotation>

</semantics>

</math></span><img src="./6cd9594a16cb898b8f2a2dff9227a385ec183392.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{2})}" loading="lazy"></span>.<sup id="cite_ref-kleinberg&Tardos_9-1" class="reference"><a href="#cite_note-kleinberg&Tardos-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Parallelism">Parallelism</h3></div>

<p>Divide-and-conquer algorithms are naturally adapted for execution in <a href="Multiprocessing" title="Multiprocessing">multi-processor</a> machines, especially <a href="Shared-memory" class="mw-redirect" title="Shared-memory">shared-memory</a> systems where the communication of data between <a href="Central_processing_unit" title="Central processing unit">processors</a> does not need to be planned in advance because distinct sub-problems can be executed on different processors.

</p>

<div class="mw-heading mw-heading3"><h3 id="Memory_access">Memory access</h3></div>

<p>Divide-and-conquer algorithms naturally tend to make efficient use of <a href="Memory_cache" class="mw-redirect" title="Memory cache">memory caches</a>. The reason is that once a sub-problem is small enough, it and all its sub-problems can, in principle, be solved within the <a href="Cache_(computing)" title="Cache (computing)">cache</a>, without accessing the slower <a href="Computer_data_storage" title="Computer data storage">main memory</a>. An algorithm designed to exploit the cache in this way is called <i><a href="Cache-oblivious_algorithm" title="Cache-oblivious algorithm">cache-oblivious</a></i>, because it does not contain the cache size as an explicit <a href="Parameter_(computer_programming)" title="Parameter (computer programming)">parameter</a>.<sup id="cite_ref-cahob_10-0" class="reference"><a href="#cite_note-cahob-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> Moreover, D&C algorithms can be designed for important algorithms (e.g., sorting, FFTs, and matrix multiplication) to be <i>optimal</i> cache-oblivious algorithms–they use the cache in a probably optimal way, in an asymptotic sense, regardless of the cache size. In contrast, the traditional approach to exploiting the cache is <i>blocking</i>, as in <a href="Loop_nest_optimization" title="Loop nest optimization">loop nest optimization</a>, where the problem is explicitly divided into chunks of the appropriate size—this can also use the cache optimally, but only when the algorithm is tuned for the specific cache sizes of a particular machine.

</p><p>The same advantage exists with regards to other hierarchical storage systems, such as <a href="Non-uniform_memory_access" title="Non-uniform memory access">NUMA</a> or <a href="Virtual_memory" title="Virtual memory">virtual memory</a>, as well as for multiple levels of cache: once a sub-problem is small enough, it can be solved within a given level of the hierarchy, without accessing the higher (slower) levels.

</p>

<div class="mw-heading mw-heading3"><h3 id="Roundoff_control">Roundoff control</h3></div>

<p>In computations with rounded arithmetic, e.g. with <a href="Floating-point" class="mw-redirect" title="Floating-point">floating-point</a> numbers, a divide-and-conquer algorithm may yield more accurate results than a superficially equivalent iterative method. For example, one can add <i>N</i> numbers either by a simple loop that adds each datum to a single variable, or by a D&C algorithm called <a href="Pairwise_summation" title="Pairwise summation">pairwise summation</a> that breaks the data set into two halves, recursively computes the sum of each half, and then adds the two sums. While the second method performs the same number of additions as the first and pays the overhead of the recursive calls, it is usually more accurate.<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Implementation_issues">Implementation issues</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Recursion">Recursion</h3></div>

<p>Divide-and-conquer algorithms are naturally implemented as <a href="Recursion_(computer_science)" title="Recursion (computer science)">recursive procedures</a>. In that case, the partial sub-problems leading to the one currently being solved are automatically stored in the <a href="Call_stack" title="Call stack">procedure call stack</a>. A recursive function is a function that calls itself within its definition.

</p>

<div class="mw-heading mw-heading3"><h3 id="Explicit_stack">Explicit stack</h3></div>

<p>Divide-and-conquer algorithms can also be implemented by a non-recursive program that stores the partial sub-problems in some explicit data structure, such as a <a href="Stack_(data_structure)" class="mw-redirect" title="Stack (data structure)">stack</a>, <a href="Queue_(data_structure)" class="mw-redirect" title="Queue (data structure)">queue</a>, or <a href="Priority_queue" title="Priority queue">priority queue</a>. This approach allows more freedom in the choice of the sub-problem that is to be solved next, a feature that is important in some applications — e.g. in <a href="Breadth_first_recursion" class="mw-redirect" title="Breadth first recursion">breadth-first recursion</a> and the <a href="Branch-and-bound" class="mw-redirect" title="Branch-and-bound">branch-and-bound</a> method for function optimization. This approach is also the standard solution in programming languages that do not provide support for recursive procedures.

</p>

<div class="mw-heading mw-heading3"><h3 id="Stack_size">Stack size</h3></div>

<p>In recursive implementations of D&C algorithms, one must make sure that there is sufficient memory allocated for the recursion stack, otherwise, the execution may fail because of <a href="Stack_overflow" title="Stack overflow">stack overflow</a>. D&C algorithms that are time-efficient often have relatively small recursion depth. For example, the quicksort algorithm can be implemented so that it never requires more than <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{2}n}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log _{2}n}</annotation>

</semantics>

</math></span><img src="./d74677fc45e0d926639433586327cbc2982eae89.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.808ex; height:2.676ex;" alt="{\displaystyle \log _{2}n}" loading="lazy"></span> nested recursive calls to sort <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</p><p>Stack overflow may be difficult to avoid when using recursive procedures since many compilers assume that the recursion stack is a contiguous area of memory, and some allocate a fixed amount of space for it. Compilers may also save more information in the recursion stack than is strictly necessary, such as return address, unchanging parameters, and the internal variables of the procedure. Thus, the risk of stack overflow can be reduced by minimizing the parameters and internal variables of the recursive procedure or by using an explicit stack structure.

</p>

<div class="mw-heading mw-heading3"><h3 id="Choosing_the_base_cases">Choosing the base cases</h3></div>

<p>In any recursive algorithm, there is considerable freedom in the choice of the <i>base cases</i>, the small subproblems that are solved directly in order to terminate the recursion.

</p><p>Choosing the smallest or simplest possible base cases is more elegant and usually leads to simpler programs, because there are fewer cases to consider and they are easier to solve. For example, a <a href="Fast_Fourier_transform" title="Fast Fourier transform">Fast Fourier Transform</a> algorithm could stop the recursion when the input is a single sample, and the quicksort list-sorting algorithm could stop when the input is the empty list; in both examples, there is only one base case to consider, and it requires no processing.

</p><p>On the other hand, efficiency often improves if the recursion is stopped at relatively large base cases, and these are solved non-recursively, resulting in a <a href="Hybrid_algorithm" title="Hybrid algorithm">hybrid algorithm</a>. This strategy avoids the overhead of recursive calls that do little or no work and may also allow the use of specialized non-recursive algorithms that, for those base cases, are more efficient than explicit recursion. A general procedure for a simple hybrid recursive algorithm is <i>short-circuiting the base case</i>, also known as <i><a href="Arm's-length_recursion" class="mw-redirect" title="Arm's-length recursion">arm's-length recursion</a></i>. In this case, whether the next step will result in the base case is checked before the function call, avoiding an unnecessary function call. For example, in a tree, rather than recursing to a child node and then checking whether it is null, checking null before recursing; avoids half the function calls in some algorithms on binary trees. Since a D&C algorithm eventually reduces each problem or sub-problem instance to a large number of base instances, these often dominate the overall cost of the algorithm, especially when the splitting/joining overhead is low. Note that these considerations do not depend on whether recursion is implemented by the compiler or by an explicit stack.

</p><p>Thus, for example, many library implementations of quicksort will switch to a simple loop-based <a href="Insertion_sort" title="Insertion sort">insertion sort</a> (or similar) algorithm once the number of items to be sorted is sufficiently small. Note that, if the empty list were the only base case, sorting a list with <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> entries would entail maximally <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> quicksort calls that would do nothing but return immediately. Increasing the base cases to lists of size 2 or less will eliminate most of those do-nothing calls, and more generally a base case larger than 2 is typically used to reduce the fraction of time spent in function-call overhead or stack manipulation.

</p><p>Alternatively, one can employ large base cases that still use a divide-and-conquer algorithm, but implement the algorithm for predetermined set of fixed sizes where the algorithm can be completely <a href="Loop_unwinding" class="mw-redirect" title="Loop unwinding">unrolled</a> into code that has no recursion, loops, or <a href="Conditional_(programming)" class="mw-redirect" title="Conditional (programming)">conditionals</a> (related to the technique of <a href="Partial_evaluation" title="Partial evaluation">partial evaluation</a>). For example, this approach is used in some efficient FFT implementations, where the base cases are unrolled implementations of divide-and-conquer FFT algorithms for a set of fixed sizes.<sup id="cite_ref-fftw_12-0" class="reference"><a href="#cite_note-fftw-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> <a href="Source-code_generation" class="mw-redirect" title="Source-code generation">Source-code generation</a> methods may be used to produce the large number of separate base cases desirable to implement this strategy efficiently.<sup id="cite_ref-fftw_12-1" class="reference"><a href="#cite_note-fftw-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup>

</p><p>The generalized version of this idea is known as recursion "unrolling" or "coarsening", and various techniques have been proposed for automating the procedure of enlarging the base case.<sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Dynamic_programming_for_overlapping_subproblems">Dynamic programming for overlapping subproblems</h3></div>

<p>For some problems, the branched recursion may end up evaluating the same sub-problem many times over. In such cases it may be worth identifying and saving the solutions to these overlapping subproblems, a technique which is commonly known as <a href="Memoization" title="Memoization">memoization</a>. Followed to the limit, it leads to <a href="Bottom-up_design" class="mw-redirect" title="Bottom-up design">bottom-up</a> divide-and-conquer algorithms such as <a href="Dynamic_programming" title="Dynamic programming">dynamic programming</a>.

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .infobox .side-box{font-size:100%}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1237033735">

/* start https://en.wikipedia.org/ */

@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}

/* end https://en.wikipedia.org/ */

</style><div class="side-box side-box-right sistersitebox"><style data-mw-deduplicate="TemplateStyles:r1126788409">

/* start https://en.wikipedia.org/ */

.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}

/* end https://en.wikipedia.org/ */

</style>

<div class="side-box-text plainlist">Wikimedia Commons has media related to <span style="font-weight: bold; font-style: italic;"><a href="https://commons.wikimedia.org/wiki/Category:Divide-and-conquer_algorithms" class="extiw external" title="commons:Category:Divide-and-conquer algorithms">Divide-and-conquer algorithms</a></span>.</div></div>

</div>

<ul><li><a href="Akra%E2%80%93Bazzi_method" title="Akra–Bazzi method">Akra–Bazzi method</a> – Method in computer science</li>

<li><a href="Decomposable_aggregation_function" class="mw-redirect" title="Decomposable aggregation function">Decomposable aggregation function</a> – Type of function in database management<span style="display:none" class="category-annotation-with-redirected-description">Pages displaying short descriptions of redirect targets</span></li>

<li><a href="Divide_and_conquer" title="Divide and conquer">"Divide and conquer"</a> – Strategy in politics and sociology</li>

<li><a href="Fork%E2%80%93join_model" title="Fork–join model">Fork–join model</a> – Way of setting up and executing parallel computer programs</li>

<li><a href="Master_theorem_(analysis_of_algorithms)" title="Master theorem (analysis of algorithms)">Master theorem (analysis of algorithms)</a> – Tool for analyzing divide-and-conquer algorithms</li>

<li><a href="Mathematical_induction" title="Mathematical induction">Mathematical induction</a> – Form of mathematical proof</li>

<li><a href="MapReduce" title="MapReduce">MapReduce</a> – Parallel programming model</li>

<li><a href="Heuristic_(computer_science)" title="Heuristic (computer science)">Heuristic (computer science)</a> – Type of algorithm, produces approximately correct solutions</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFBlahut2014" class="citation book cs1"><a href="Richard_Blahut" title="Richard Blahut">Blahut, Richard</a> (14 May 2014). <i>Fast Algorithms for Signal Processing</i>. Cambridge University Press. pp. <span class="nowrap">139–</span>143. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-511-77637-3</bdi>.</cite></span>

</li>

<li id="cite_note-CormenLeiserson2009-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-CormenLeiserson2009_2-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFThomas_H._CormenCharles_E._LeisersonRonald_L._RivestClifford_Stein2009" class="citation book cs1">Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (31 July 2009). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=aefUBQAAQBAJ&q=%22Divide-and-conquer%22"><i>Introduction to Algorithms</i></a>. MIT Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-262-53305-8</bdi>.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text">Brassard, G., and Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.</span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text">Anany V. Levitin, <i>Introduction to the Design and Analysis of Algorithms</i> (Addison Wesley, 2002).</span>

</li>

<li id="cite_note-Knuth3-5"><span class="mw-cite-backlink">^ <a href="#cite_ref-Knuth3_5-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Knuth3_5-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-Knuth3_5-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text">Donald E. Knuth, <i>The Art of Computer Programming: Volume 3, Sorting and Searching</i>, second edition (Addison-Wesley, 1998).</span>

</li>

<li id="cite_note-Heideman84-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-Heideman84_6-0">^</a></b></span> <span class="reference-text">Heideman, M. T., D. H. Johnson, and C. S. Burrus, "<a rel="nofollow" class="external text" href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.331.4791&rep=rep1&type=pdf">Gauss and the history of the fast Fourier transform</a>", IEEE ASSP Magazine, 1, (4), 14–21 (1984).</span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><cite id="CITEREFKnuth1998" class="citation book cs1"><a href="Donald_Knuth" title="Donald Knuth">Knuth, Donald</a> (1998). <span class="id-lock-limited" title="Free access subject to limited trial, subscription normally required"><a rel="nofollow" class="external text" href="https://archive.org/details/artofcomputerpro03knut"><i>The Art of Computer Programming: Volume 3 Sorting and Searching</i></a></span>. Addison-Wesley. p. <a rel="nofollow" class="external text" href="https://archive.org/details/artofcomputerpro03knut/page/159">159</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-89685-0</bdi>.</cite></span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><cite id="CITEREFKaratsubaYuri_P._Ofman1962" class="citation journal cs1"><a href="Anatolii_Alexeevitch_Karatsuba" class="mw-redirect" title="Anatolii Alexeevitch Karatsuba">Karatsuba, Anatolii A.</a>; <a href="Yuri_Petrovich_Ofman" class="mw-redirect" title="Yuri Petrovich Ofman">Yuri P. Ofman</a> (1962). "Умножение многозначных чисел на автоматах". <i><a href="Doklady_Akademii_Nauk_SSSR" class="mw-redirect" title="Doklady Akademii Nauk SSSR">Doklady Akademii Nauk SSSR</a></i>. <b>146</b>: <span class="nowrap">293–</span>294.</cite> Translated in <cite id="CITEREFKaratsubaOfman1963" class="citation journal cs1">Karatsuba, A.; Ofman, Yu. (1963). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=MrkOAAAAIAAJ">"Multiplication of Multidigit Numbers on Automata"</a>. <i>Soviet Physics Doklady</i>. <b>7</b>: <span class="nowrap">595–</span>596. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1963SPhD....7..595K">1963SPhD....7..595K</a>.</cite></span>

</li>

<li id="cite_note-kleinberg&Tardos-9"><span class="mw-cite-backlink">^ <a href="#cite_ref-kleinberg&Tardos_9-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-kleinberg&Tardos_9-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFKleinbergTardos2005" class="citation book cs1">Kleinberg, Jon; Tardos, Eva (March 16, 2005). <a rel="nofollow" class="external text" href="https://www.pearson.com/en-us/subject-catalog/p/algorithm-design/P200000003259/9780137546350"><i>Algorithm Design</i></a> (1 ed.). <a href="Pearson_Education" title="Pearson Education">Pearson Education</a>. pp. <span class="nowrap">214–</span>220. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780321295354</bdi><span class="reference-accessdate">. Retrieved <span class="nowrap">26 January</span> 2025</span>.</cite></span>

</li>

<li id="cite_note-cahob-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-cahob_10-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFM._FrigoC._E._LeisersonH._Prokop1999" class="citation book cs1">M. Frigo; C. E. Leiserson; H. Prokop (1999). <a rel="nofollow" class="external text" href="https://dspace.mit.edu/bitstream/handle/1721.1/80568/43558192-MIT.pdf;sequence=2">"Cache-oblivious algorithms"</a>. <i>40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039)</i>. pp. <span class="nowrap">285–</span>297. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSFFCS.1999.814600">10.1109/SFFCS.1999.814600</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-7695-0409-4</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:62758836">62758836</a>.</cite></span>

</li>

<li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text">Nicholas J. Higham, "<a rel="nofollow" class="external text" href="https://pdfs.semanticscholar.org/5c17/9d447a27c40a54b2bf8b1b2d6819e63c1a69.pdf">The accuracy of floating-point summation</a>", <i>SIAM J. Scientific Computing</i> <b>14</b> (4), 783–799 (1993).</span>

</li>

<li id="cite_note-fftw-12"><span class="mw-cite-backlink">^ <a href="#cite_ref-fftw_12-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-fftw_12-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFFrigo,_M.Johnson,_S._G.2005" class="citation journal cs1">Frigo, M.; Johnson, S. G. (February 2005). <a rel="nofollow" class="external text" href="http://www.fftw.org/fftw-paper-ieee.pdf">"The design and implementation of FFTW3"</a> <span class="cs1-format">(PDF)</span>. <i>Proceedings of the IEEE</i>. <b>93</b> (2): <span class="nowrap">216–</span>231. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2005IEEEP..93..216F">2005IEEEP..93..216F</a>. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.66.3097">10.1.1.66.3097</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FJPROC.2004.840301">10.1109/JPROC.2004.840301</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:6644892">6644892</a>.</cite></span>

</li>

<li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text">Radu Rugina and Martin Rinard, "<a rel="nofollow" class="external text" href="http://people.csail.mit.edu/rinard/paper/lcpc00.pdf">Recursion unrolling for divide and conquer programs</a>" in <i>Languages and Compilers for Parallel Computing</i>, chapter 3, pp. 34–48. <i>Lecture Notes in Computer Science</i> vol. 2017 (Berlin: Springer, 2001).</span>

</li>

</ol></div></div><div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Data_structures_and_algorithms145" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Data_structures_and_algorithms145" style="font-size:114%;margin:0 4em"><a href="Data_structure" title="Data structure">Data structures</a> and <a href="Algorithm" title="Algorithm">algorithms</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Data structures</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Array_(data_structure)" title="Array (data structure)">Array</a></li>

<li><a href="Associative_array" title="Associative array">Associative array</a></li>

<li><a href="Binary_search_tree" title="Binary search tree">Binary search tree</a></li>

<li><a href="Fenwick_tree" title="Fenwick tree">Fenwick tree</a></li>

<li><a href="Graph_(abstract_data_type)" title="Graph (abstract data type)">Graph</a></li>

<li><a href="Hash_table" title="Hash table">Hash table</a></li>

<li><a href="Linked_list" title="Linked list">Linked list</a></li>

<li><a href="Queue_(abstract_data_type)" title="Queue (abstract data type)">Queue</a></li>

<li><a href="Segment_tree" title="Segment tree">Segment tree</a></li>

<li><a href="Stack_(abstract_data_type)" title="Stack (abstract data type)">Stack</a></li>

<li><a href="String_(computer_science)" title="String (computer science)">String</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Algorithms and <a href="Algorithmic_paradigm" title="Algorithmic paradigm">algorithmic paradigms</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Backtracking" title="Backtracking">Backtracking</a></li>

<li><a href="Binary_search" title="Binary search">Binary search</a></li>

<li><a href="Breadth-first_search" title="Breadth-first search">Breadth-first search</a></li>

<li><a href="Brute-force_search" title="Brute-force search">Brute-force search</a></li>

<li><a href="Depth-first_search" title="Depth-first search">Depth-first search</a></li>

<li><a href="Dynamic_programming" title="Dynamic programming">Dynamic programming</a></li>

<li><a href="Graph_traversal" title="Graph traversal">Graph traversal</a></li>

<li><a href="Greedy_algorithm" title="Greedy algorithm">Greedy</a></li>

<li><a href="Hash_function" title="Hash function">Hash function</a></li>

<li><a href="Minimax" title="Minimax">Minimax</a></li>

<li><a href="Online_algorithm" title="Online algorithm">Online</a></li>

<li><a href="Randomized_algorithm" title="Randomized algorithm">Randomized</a></li>

<li><a href="Recursion_(computer_science)" title="Recursion (computer science)">Recursion</a></li>

<li><a href="Root-finding_algorithm" title="Root-finding algorithm">Root-finding</a></li>

<li><a href="Sorting_algorithm" title="Sorting algorithm">Sorting</a></li>

<li><a href="Streaming_algorithm" title="Streaming algorithm">Streaming</a></li>

<li><a href="Sweep_line_algorithm" title="Sweep line algorithm">Sweep line</a></li>

<li><a href="String-searching_algorithm" title="String-searching algorithm">String-searching</a></li>

<li><a href="Topological_sorting" title="Topological sorting">Topological sorting</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li><a href="List_of_data_structures" title="List of data structures">List of data structures</a></li>

<li><a href="List_of_algorithms" title="List of algorithms">List of algorithms</a></li></ul>

</div></td></tr></tbody></table></div>

<p><br>

</p>

<div class="navbox-styles"></div><div role="navigation" class="navbox authority-control" aria-label="Navbox390" style="padding:3px"><table class="nowraplinks hlist navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">Authority control databases: National </th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><a rel="nofollow" class="external text" href="https://d-nb.info/gnd/4291466-8">Germany</a></span></li></ul></div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-14" href="https://en.wikipedia.org/wiki/?title=Divide-and-conquer_algorithm&oldid=1290360712">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>